#include "DTree.h"

using namespace std;

DTree::DTree()
{
    clear();
	_T = TREE();
	_VL = TreeNodeList();
	_N = 0;
//	_M = 0;
}

DTree::DTree(int N)
{
    clear();
	_T = TREE();
	_VL = TreeNodeList();
	_N = 0;
//	_M = 0;
    for (int v=0; v<N; ++v)
    {
        add_vertex(v);
    }
}

DTree::DTree(istream& in)
{
    string buf;
    getline(in, buf);
    if (buf != "graph_for_greach")
    {
        cout << "BAD FILE FORMAT!" << endl;
        exit(0);
    }

    int n;
	getline(in, buf);
	istringstream(buf) >> n;

	// initialize
	//_N = n;
	_VL = TreeNodeList(n);
	_T = TREE(n, FatherSonList());

	for (int v = 0; v < n; v++)
	{
	    add_vertex(v);
	}

	string sub;
	int idx;
	int sid = 0;
	int tid = 0;
	while (getline(in, buf)) {
		idx = buf.find(":");
		buf.erase(0, idx+2);
		while (buf.find(" ") != string::npos) {
			sub = buf.substr(0, buf.find(" "));
			istringstream(sub) >> tid;
			buf.erase(0, buf.find(" ")+1);
			add_edge(sid, tid);
		}
		++sid;
	}

}

DTree::~DTree() {}

void DTree::clear()
{
    _T.clear();
    _VL.clear();
    _N = 0;
    roots.clear();
 //   _M = 0;
}

void DTree::write_tree(ostream& out)
{
    out << "Tree size=" << number_of_vertices()<< "; #edges = " << number_of_edges() << endl;
	//out << "graph_for_greach" << endl;
    out<<"root:";
    vector<int> roots=get_roots();
    for(vector<int>::iterator it=roots.begin();it!=roots.end();it++){
    	out<<*it<<"\t";
    }
    out<<endl;

	//TREE::iterator tit;
	Children cl;
	Children::iterator cit;
	TreeNodeList::iterator vit;
	int i = 0;
	for (i = 0; i < _VL.size(); i++)
	{
		out << i << ": ";
		cl = _T[i]._sons;
		for (cit = cl.begin(); cit != cl.end(); cit++)
		{
		    out << (*cit) << " ";
		}
		out << "#" << endl;
	}
}

void DTree::add_vertex(int vid)
{
    if (vid >= _VL.size())
    {
        // insert vertices with ID less than vid
		int size = _VL.size();
		for (int i = 0; i < (vid-size+1); i++)
		{
			_T.push_back(FatherSonList());
			TreeNode vex;
			vex._ID = _N+i+1;
            vex._IntBeg = -1;
            vex._IntEnd = -1;
            vex._PreN = -1;
            vex._LmdID = vex._ID;
            vex._RangeSNTE._start = -1;
            vex._RangeSNTE._end = -1;
            vex._visited = false;
            _VL.push_back(vex);
		}
		_N = _VL.size();
	}

    // if there's already a vertex whose ID is vid, then modify it with initial values
    // if this is the new vertex insterted, then modify it also
    TreeNode vex;
    vex._ID = vid;
    vex._IntBeg = -1;
    vex._IntEnd = -1;
    vex._PreN = -1;
    vex._LmdID = vex._ID;
    vex._RangeSNTE._start = -1;
    vex._RangeSNTE._end = -1;
    vex._visited = false;
    _VL[vid] = vex;

    FatherSonList fs;
	Children cl = Children();
	fs._father = -1;
	fs._sons = cl;
	_T[vex._ID] = fs;
}

bool DTree::remove_vertex(int vid)
{
    // not allowed to remove vertices whose ID is smaller than _N-1
    // because only adding a virtual node to a forest is possible
    if (vid != _VL.size()-1)
        return false;

    Children& cl = children_of(vid);
/*
 * This doesn't work because remove_edge invokes vector::erase which inturn
 * causes the iterator cit to be invalid as cl refers to _T[vid]._sons
    // remove involved tree edges
    for (Children::iterator cit=cl.begin(); cit!=cl.end(); ++cit)
    {
        int w = *cit;
        remove_edge(vid, w);
    }
*/
    // Set the _father member of vid's children to -1
    for (Children::iterator cit=cl.begin(); cit!=cl.end(); ++cit)
    {
        int w = *cit;
        //remove_edge(vid, w);  // do not call remove_edge
        _T[w]._father = -1;
    }
    // Remove all the tree edges involved in vid
    _T.erase(_T.end()-1);
    _VL.erase(_VL.end()-1);
    _N = _VL.size();
}


///
/// For now on need to modify
///
bool DTree::add_edge(int src, int trg)
{
    if (src>=_N || trg>=_N)
        return false;
    else
    {
        vector<int>::iterator eit;
        for (eit=_T[src]._sons.begin(); eit!=_T[src]._sons.end();++eit)
        // check that whether the edge <src,trg> has already been added to the tree
        {
            if (*eit == trg)
                break;
        }
        if (eit == _T[src]._sons.end())
        // not exists, do a further check to decide whether add it or discard it
        {
            if (_T[trg]._father == -1)
            {
                _T[src]._sons.push_back(trg);
                _T[trg]._father = src;
//                ++_M;
                return true;
            }
            else
                return false;
        }
        else
            return false;
    }
}

bool DTree::remove_edge(int src, int trg)
{
    if (src>=_N || trg>=_N)
        return false;
    else
    {
        Children::iterator eit;

        // to check whether edge <src, tgr> exists
        eit = find(_T[src]._sons.begin(), _T[src]._sons.end(), trg);
        if (eit != _T[src]._sons.end())
        {   // exists, remove trg from _T[src]._sons
            _T[src]._sons.erase(eit);
            // change _T[trg]._father to nil
            _T[trg]._father = -1;
            return true;
        }
        else    // not exists
            return false;
    }
}

int DTree::number_of_vertices()
{
    return _N;
}

int DTree::number_of_edges()
{
    //return _M;
    Children cl;
	TREE::iterator tit;
	int num = 0;
	for (tit = _T.begin(); tit != _T.end(); tit++)
	{
		cl = tit->_sons;
		num += cl.size();
	}
	return num;
}

TreeNodeList& DTree::get_vertices()
{
    return _VL;
}

Children& DTree::children_of(int vid)
{
    return _T[vid]._sons;
}

int DTree::father_of(int vid)
{
    return _T[vid]._father;
}

int DTree::out_degree_of(int vid)
{
    if (vid >= _N)
        return -1;  // this vertex does not exist
    else
        return _T[vid]._sons.size();
}

int DTree::in_degree_of(int vid)
{
    if (vid >= _N)
        return -1;  // this vertex does not exist
    else if (_T[vid]._father == -1)
        return 0;
    else
        return 1;
}

vector<int> DTree::get_roots()
{

	return roots;
//    vector<int> r;
//    for (int vid=0; vid<_N; ++vid)
//    {
//        if (in_degree_of(vid) == 0)
//            r.push_back(vid);
//    }
//
//    return r;
}

bool DTree::has_edge(int src, int trg)
{
	if (_T[trg]._father != src)
	    return false;
	else
	    return true;

}

DTree& DTree::operator=(const DTree& dt)
{
    if (this != &dt)
    {
		_T = dt._T;
		_VL = dt._VL;
		_N = dt._N;
//		_M = dt._M;
    }
	return *this;
}

TreeNode& DTree::operator[](const int vid)
{
    return _VL[vid];
}

void DTree::addRoots(int root){
	roots.push_back(root);
}
